package com.leetcode.根据算法进行分类.单调栈相关;

import java.util.ArrayDeque;
import java.util.HashSet;

/**
 * @author: xiaomi
 * @date: 2021/2/12
 * @description: 316. 去除重复字母
 * https://leetcode-cn.com/problems/remove-duplicate-letters/
 */
public class B_316_去除重复字母 {

    public static void main(String[] args) {
        B_316_去除重复字母 action = new B_316_去除重复字母();
        test1(action);
        test2(action);
        test3(action);
    }

    public static void test1(B_316_去除重复字母 action) {
        //abc
        String s = "bcabc";
        String res = action.removeDuplicateLetters(s);
        System.out.println("res = " + res);
    }

    public static void test2(B_316_去除重复字母 action) {
        //acdb
        String s = "cbacdcbc";
        String res = action.removeDuplicateLetters(s);
        System.out.println("res = " + res);

    }

    public static void test3(B_316_去除重复字母 action) {
        //cdadabcc
        String s = "cdadabcc";
        String res = action.removeDuplicateLetters(s);
        System.out.println("res = " + res);
    }


    /**
     * 我能想到的解决方案：
     * 1.先 遍历一遍，记录每个小写字母的数量；
     * 2.如果字母是顺序的就是稳定的，可以直接出栈；当
     *
     * @param s
     * @return
     */
    public String removeDuplicateLetters(String s) {
        //1.第一步记录出现的次数
        //由于 a-z 对应 ASCII 是 97-122 所以可以直接开 123 避免 -'a' 的计算
        int[] recordArr = new int[123];
        char[] chars = s.toCharArray();
        int len = chars.length;
        for (int i = 0; i < len; i++) {
            recordArr[chars[i]]++;
        }
        //
        ArrayDeque<Character> stack = new ArrayDeque<>();
        //通过调试中发现自己给出的方案存在漏洞，于是通过增加一个 set 来记录 stack 中已经存在的元素
        HashSet<Character> set = new HashSet<>();
        for (int i = 0; i < len; i++) {
            Character curChar = chars[i];
            if (stack.isEmpty() || (curChar > stack.peekLast() && !set.contains(curChar))) {
                //当前大于 栈顶元素时，属于稳定的结构
                stack.addLast(curChar);
                set.add(curChar);
                continue;
            }
            if (curChar.equals(stack.peekLast())) {
                recordArr[chars[i]]--;
            } else if (!set.contains(curChar)){
                //此时 chars[i] < 栈顶元素 && 是新的元素
                while (!stack.isEmpty() && recordArr[stack.peekLast()] > 1) {
                    Character last = stack.removeLast();
                    recordArr[last]--;
                    set.remove(last);
                    if (stack.isEmpty() || curChar >= stack.peekLast()) {
                        break;
                    }
                }
                if (curChar.equals(stack.peekLast())) {
                    continue;
                }
                if (!set.contains(curChar)){
                    stack.addLast(curChar);
                    set.add(curChar);
                }else {
                    recordArr[curChar]--;
                }
            }else {
                recordArr[curChar]--;
            }
        }
        //最后将栈中的元素逆序组装
        int size = stack.size();
        char[] resChars = new char[size];
        for (int i = size - 1; i >= 0; i--) {
            resChars[i] = stack.removeLast();
        }
        return new String(resChars);
    }


}
